package likouJava;

import java.util.HashMap;

public class LRU缓存 {

        //定义双向链表节点
        class  Node{
            int key, value;
            Node prev, next;
            Node(int k, int v) {
                key = k;
                value = v;
            }
        }

        private HashMap<Integer, Node> map;
        private int capacity;
        private Node head, tail;  //伪头尾节点
    public void LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.next =head;
    }
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node node = map.get(key);
        //移动到链表头
        remove(node);
        insertToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            //更新已经有节点的值，并且移动到头
            Node node = map.get(key);
            node.value = value;
            remove(node);
            insertToHead(node);
        }else {
            if(map.size() == capacity){
                //淘汰末尾节点
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
            //插入新节点
            Node node = new Node(key, value);
            map.put(key, node);
            insertToHead(node);

        }
    }

    //插入到头节点后
    private void insertToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    //删除节点
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


}
